package com.zklh.leetcode.dynamic.middle.problem64;

/**
 * @ClassName Solution
 * @Description
 * @Author 坐看落花
 * @Date 2020/3/19 16:04
 * @Version 1.0
 **/
public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int distance = 1;
        int maxDistance = grid[0].length+grid.length-2;

        // 定义当前结点的坐标, x表示内层数组的索引,
        // y表示外层数组的索引(其实无所谓, 都一样, 但是抽象的越具体思考起来越简单)
        // x表示距离左上结点的横向距离, y表示距离左上结点的纵向距离
        int x = 0, y = 0;
        // 定义x,y坐标的最大值, 防止越界,可能会用不到
        int maxX = grid[0].length-1, maxY = grid.length-1;
        // 定义上和左结点的最小值
        int topMin = 0, leftMin = 0;
        for (; distance <= maxDistance; distance++) {
            // 这里就是表示距离左上结点的某个距离一层最小距离的获取
            for (x = distance;x >= 0; x--) {
                y = distance-x;
                // 表示x或者y越界, 此时直接continue
                if (x > maxX || y > maxY){
                    continue;
                }
                // 这里表示如果当前结点是上或者左边界则通过上或左无法到达, 也就是取最大值
                topMin = (y-1 >= 0 ? grid[y-1][x] : Integer.MAX_VALUE);
                leftMin = (x-1 >= 0 ? grid[y][x-1] : Integer.MAX_VALUE);
                // 取左和上结点中最小的路径值
                grid[y][x] += topMin < leftMin ? topMin : leftMin;
            }
        }

        return grid[maxY][maxX];
    }

    public static void main(String[] args){
        int[][] grid = {
                {1,3,1},
                {1,5,1},
                {4,2,1},
        };
        Solution solution = new Solution();
        System.out.println(solution.minPathSum(grid));
    }

}
